import heapq


# graph是图的邻接表 start为起点
def dijkstra(graph, start):
    # 初始化所有的节点的距离为无穷大
    distance = {node: float("inf") for node in graph}
    # 起点到自身的距离为0
    distance[start] = 0
    # 创建一个集合用于记录已访问过的节点
    visited = set()
    # 初始化最小堆 存的是(距离,节点)元组 初始为(0, 起点)
    heap = [(0, start)]
    # 当堆不为空的时候
    while heap:
        print(heap)
        # 弹出堆顶的元素，获取当前节点到A的距离，以及当前的节点
        curr_distance, curr_node = heapq.heappop(heap)
        # 如果当前节点已经访问过了，则跳过
        if curr_node in visited:
            continue
        # 标记为当前的节点已经访问过了
        visited.add(curr_node)
        # 遍历当前的节点的所有的邻居
        for neighbor, weight in graph[curr_node]:
            # 如果此邻居未访问过
            if neighbor not in visited:
                # 计算从起点到邻居的距离
                new_distance = curr_distance + weight
                # 如果新距离小于已知的距离
                if new_distance < distance[neighbor]:
                    # 则更新为新的距离
                    distance[neighbor] = new_distance
                    # 将新的距离和邻居结点加入最小堆
                    heapq.heappush(heap, (new_distance, neighbor))
    return distance


# 定义图的邻接表，节点为大写字母，边带权重
graph = {
    "A": [("B", 2), ("C", 5)],
    "B": [("C", 1), ("D", 3)],
    "C": [("D", 3), ("E", 4), ("F", 1)],
    "D": [("E", 1), ("F", 4)],
    "E": [("F", 1)],
    "F": [],
}
# 调用dijkstra函数，计算A到各点的最短距离，并输出结果
print(dijkstra(graph, "A"))  # 输出A到各点的最短距离
